package com.nowcoder.Offer.Tree;

import org.junit.Test;

/**
 * 判断是否是二叉搜索树后序遍历的结果
 */
public class VerifySquenceOfBST {

    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0) return false;
        return verifyHelper(sequence,0,sequence.length-1);
    }

    public boolean verifyHelper(int[] seq, int leftHead,  int root){
        if(leftHead >= root) return true;
        int left = leftHead;
        while(seq[leftHead] < seq[root])
            leftHead++;

        int rightHead = leftHead ;
        int right = rightHead;

        while(seq[rightHead] > seq[root]){
            rightHead++;
        }

        return rightHead == root
                && verifyHelper(seq,left,leftHead-1)
                && verifyHelper(seq,right,root-1);
    }

    @Test
    public void test(){
        int[] arr = {4,8,6,12,16,14,10};
        System.out.println(VerifySquenceOfBST(arr));
    }
}
